package hot.twoIndex;
/**
 * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
 *
 * 注意：答案中不可以包含重复的三元组。
 *
 *
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 * 解释：
 * nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
 * nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
 * nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
 * 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
 * 注意，输出的顺序和三元组的顺序并不重要。
 * 示例 2：
 *
 * 输入：nums = [0,1,1]
 * 输出：[]
 * 解释：唯一可能的三元组和不为 0 。
 * 示例 3：
 *
 * 输入：nums = [0,0,0]
 * 输出：[[0,0,0]]
 * 解释：唯一可能的三元组和为 0 。
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//三数之和，如果我们固定某个数后，那么问题转化为两数之和，
//固遍历数组，然当前数后两数求两数之和(双指针)，同时结合剪枝等条件
public class A15 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        //判断是否存在三数之和等于0
        //三指针
        Arrays.sort(nums);
        int n=nums.length;
for(int i=0;i<n-2;i++){
    int val=nums[i];
    //剪枝
      //重复
    if(i!=0&&val==nums[i-1])continue;
    //当前值太过于小，以至于不能使得条件成立
    if(val+nums[n-1]+nums[n-2]<0) continue;
    //答案收集完毕
    if(val+nums[i+1]+nums[i+2]>0)break;
    int j=i+1;
    int k=n-1;
    while(j<k){
        int num=val+nums[j]+nums[k];
        if(num>0){
            k--;
        }
        else if(num<0){
            j++;
        }
        else{
            //添加到集合中
            res.add(List.of(val,nums[j],nums[k]));
            //继续向里面查找
            j++;
            k--;
            while(j<k&&nums[j]==nums[j-1])j++;
            while(j<k&&nums[k]==nums[k+1])k--;
        }
//双指针，在j到k求成立值
    }
}

return res;
    }
}
